/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        if(!pHead || !(pHead->next))
            return nullptr;
        ListNode lessHead(0);
        ListNode bigHead(0);
        ListNode* less = &lessHead;
        ListNode* big = &bigHead;
        while(pHead){
            if(pHead->val < x){
                less->next = pHead;
                less = less->next;
            }
            else{
                big->next = pHead;
                big = big->next;
            }
            pHead = pHead->next;
        }
        big->next = nullptr;
        less->next = bigHead.next;
        return lessHead.next;
    }
};